The present invention relates to wireless communication systems having multi-antenna base stations, and, in particular, to a scheduling method for such wireless communication systems allowing improved multiple input multiple output (MIMO) operation.
Multiple antenna wireless systems can increase the number of separate communication channels that can be provided between a given transmitter and receiver. Multiple antennas on either of a transmitter or receiver allow creation of channels that are spatially selective using a process termed “beam forming.” In multi-user beam forming, a beam-forming vector wi is created for each user i up to a maximum number of users or channels equal to the number of antennas on the transmitter. Each vector wi provides a phase and amplitude (expressed as a complex number) for transmission over each antenna element selected to allow simultaneous communication over different channels with a signal to interference and noise ratio (SINR) at each receiver above a specified threshold. This type of multi-user communication is commonly referred to as space division multiple access (SDMA).
Choosing the optimal beam forming vectors wi requires solving a difficult non-convex optimization problem. Accordingly, a simpler form of multi-user beam forming employs zero forcing beam forming (ZFBF) in which the channels wi are selected to provide zero interference with each other.
Space division multiple access may be used with other multiplexing techniques, such as time division multiplexing and frequency division multiplexing including frequency hopping or spread spectrum techniques that can allow multiple users to be served by each ZFBF channels.
At any given time, a ZFBF base station transceiver with a given number of logical channels may need to serve a pool of users greater than the number of channels. It is desirable in such circumstances to maximize the aggregate data rate of all channels by proper selection of which users to serve or “enroll” in communication. For example, one may want to maximize the aggregate data rate to provide efficient use of the transmitting equipment and on average, allow the transmitting equipment to accommodate a larger number of typical users. Other channel allocation strategies looking at fairness, quality of service, or the like, may also be used.
While determining the vectors wi for a given set of users i using ZFBF is relatively simple, determining the optimal user subset i from a pool of M can quickly become mathematically intractable. Such a search involves a space of size equation
            ∑              i        =        1            Nt        ⁢          (                                    M                                                i                              )                  where      ⁢                          (                                    M                                                i                              )        =                  M        !                              i          !                ⁢                              (                          M              -              i                        )                    !                    
Optimizations requiring an exhaustive search with a pool size as small as twelve in the time frames required by modern communication systems are currently impossible.
In addition to the mathematical complexity of the optimization process, the optimization requires a communication overhead, that is, additional data that must be communicated between the base station and mobile stations outside the data communicated by the users of the two nodes, for example, voice data in a phone system.
Referring now to FIG. 1, a base station 10 with, for example, four antennas 12a-12d may communicate with a pool of six mobile stations 14a-14f. In the optimization problem, a test signal 16a-16d must be sent from each antenna 12a-12d to single antennas (in this example) on mobile stations 14a-14f. 
The test signals 16a-16d characterize the quality of a channel between each antenna 12a-12d of the base station 10 and each individual mobile station 14. This information is collected in logical channel-characterizing vector tables 18a-18f, one for each of the mobile stations 14a-14f. In this example, each of the six channel-characterizing vector tables 18 includes four channel characterizing vectors 20, one for each of the test signals 16a-16d and thus one for each of the antennas 12a-12d. All of this data must be transmitted from the mobile stations 14a-14f to the base station 10 so that the base station 10 can identify the optimum subset of users. As the pool of users grows, this transmission overhead, to the extent that it subtracts from the aggregate data rate or other metric, can overwhelm the benefits obtainable from the optimization process.
The problem of complexity in selecting an optimum subset of users i from a pool M for beam forming transmissions may be handled, to some extent, by mathematical approximations which reduce the search space at the cost of possibly arriving at a sub-optimal solution. Such mathematical approximations do not solve the problems of data overhead for large pool sizes M.